Packets with various purposes are carried over networks and have their communication quality determined by QoS (Quality of Service) control according to traffic types. The QoS control denotes techniques that enable effective use of limited network resources, such as line bandwidth and queue buffer capacity.
As one of such QoS control techniques, a packet congestion avoidance algorithm called RED (Random Early Discarding (Detection)) has been known. The RED is a technique wherein packets arriving at a network device are stored in a queue, the amount of data stored in the queue is periodically monitored to calculate a queue elongation trend (increase/decrease in the amount of data stored in the queue), and before the queue overflows, arrival packets are discarded at random with a probability set as needed, to avoid the overflow of the queue. The RED algorithm is especially effective in processing Ethernet (registered trademark) frames and the like, which are random-length packets, rather than fixed-length packets.
As conventional RED-based packet discarding techniques, a technique has been known wherein an approximate discard probability curve is generated to perform congestion control so that the packet discarding process can be controlled by hardware (Japanese Laid-open Patent Publication No. 2005-94392 (paragraph nos. [0015] to [0018], FIG. 1)).
In the RED-based packet discarding process, packets are discarded in accordance with a discard probability curve which is indicative of an arrival packet discard probability dependent on the degree of elongation of the queue length. As a result of the recent tendency toward higher-speed, larger-capacity networks, there has been a demand for techniques capable of speeding up the packet discarding process.
Generally, in the conventional RED-based packet discarding process, hardware and firmware (software) are used in combination to execute the process. With such configuration, however, the communication time necessary for the communication between the hardware and the firmware poses an impediment to higher-speed processing. Also, since multiplications, divisions and like operations are performed by the firmware with the use of a microcomputer or a DSP (Digital Signal Processor), it is not possible to carry out packet-by-packet discarding at high speed, posing a problem that the processing speed is not high enough to support high-speed networks.
In the aforementioned conventional technique (Japanese Laid-open Patent Publication No. 2005-94392), on the other hand, the RED-based packet discarding process is implemented by hardware, thus enabling high-speed random discarding of packets. However, for convenience of circuit design, the vertical and horizontal axes of the discard probability curve are divided using binary numbers to generate a stepwise discard probability curve, and packets are discarded in accordance with the approximated discard probability curve. Thus, compared with the packet discarding process using the original linear discard probability curve, a problem arises in that the discarding error is significantly large.